from Crypto.Util.number import *
from gmpy2 import *

a = 10399034381787849923326924881454040531711492204619924608227265350044149907274051734345037676383421545973249148286183660679683016947030357640361405556516408
b = 6004903250672248020273453078045186428048881010508070095760634049430058892705564009054400328070528434060550830050010084328522605000400260581038846465000861
n = 100457237809578238448997689590363740025639066957321554834356116114019566855447194466985968666777662995007348443263561295712530012665535942780881309520544097928921920784417859632308854225762469971326925931642031846400402355926637518199130760304347996335637140724757568332604740023000379088112644537238901495181
c = 49042009464540753864186870038605696433949255281829439530955555557471951265762643642510403828448619593655860548966001304965902133517879714352191832895783859451396658166132732818620715968231113019681486494621363269268257297512939412717227009564539512793374347236183475339558666141579267673676878540943373877937

def fun(k, p0, q0):
    if (p0 * q0) % (10 ** (k + 1)) == n % (10 ** (k + 1)):
        pq0.append((p0, q0))

a0 = str(a)
b0 = str(b)
pq0 = [(0, 0)]
for k in range(len(b0)):
    pq, pq0 = pq0, [(0, 0)]
    for i in range(10):
        for j in range(10):
            if (i + j) % 10 == int(a0[-k - 1]) and (i * j) % 10 == int(b0[-k - 1]):
                for (p, q) in pq:
                    p = (p + i * 10 ** k)
                    q = (q + j * 10 ** k)
                    fun(k, p, q)
#print(pq0)
p = int('1' + str(pq0[1][0]))
q = pq0[1][1]
#p=12092931636613623040737253079065768977037831274116990695362696899634198318309588587556607732878944639910799730236593646983127255905400637167879667181506829
#q=8307103755174226983699771812499382664784661030503034013965679561410051699975573257899430944515587916063550418050690024796566861042630720583592848475010689
phi = (p - 1) * (q - 1)
d = inverse(65537, phi)
m = pow(c, d, n)
flag = long_to_bytes(m).decode()
print(flag) # flag{a4e3676e1e340581f7018972dd1905be}